The understanding of the invention requires an appreciation of what bit-serial and digit-serial signal processing procedures are. In bit-serial computation, data streams arrive at various computational elements a single bit at a time rather than a digital word at a time as in a fully parallel architecture. Bit-serial architectures generate a single bit of output in each fundamental clock cycle. The advantage of bit-serial architecture is that it is very simple to implement and to design and consumes very little die area in integrated-circuit devices. Bit-serial architectures have often been perceived as having a disadvantage not only of a long latency time, but also the disadvantage of a low throughput even after the pipeline delay latency period has elapsed.
The inventors in U.S. patent application Ser. No. 182,602, filed 18 April 1988, entitled "A CELL STACK FOR VARIABLE DIGIT WIDTH SERIAL ARCHITECTURE" and assigned to General Electric Company indicate that optimal results in terms of throughput and die area require an architecture which draws upon both parallel and serial computational philosophies. That is, in general, optimal design requires the utilization of digit-serial architectural circuit designs. In these designs, digits having a plurality N in number of parallel bits are processed in a serial fashion. Thus, in digit-serial architecture, a data word will have a number W of bits that is a multiple M times N so that data word can be divided into an integral number of digits of N-bit width. Initially, N may be chosen to be 2, 3, 4, 5, 6 or more bits, but thereafter the chosen value of N is maintained fixed. Arithmetic data flow within the circuit is over digit-wide signal lines and is propagated with the least significant digit first. Accordingly, data arrives serially at each operator, one digit at a time. Arithmetic and logic operators perform digit-serial calculations on this data and provide digit-serial output. To exploit this architecture fully, it is necessary to accommodate arbitrary digit widths up to some reasonable maximum, N.sub.max. Typically, N.sub.max is 12 or 16, but N.sub.max is not limited thereto. However, once an optimal digit width is determined for a particular signal processing system which is to be implemented on one or more integrated circuit chips, the digit width is fixed for circuit components appearing on that chip.
In the design of circuit chips to carry out digit-serial processing, it is desirable to employ combinations of hardware and software generally referred to as "silicon compilers". In general, the role of a silicon compiler is to accept from a human operator specified signal processing functions and to produce from these specifications a plurality of integrated circuit masks. These masks when employed in the proper sequence and in accordance with accepted integrated circuit processing methods, produce an electronic integrated circuit chip implementing the specified signal processing function in a given semiconductor technology and architecture. The architecture of relevance herein is the digit-serial architecture and, more particularly, the realization of a digital multiplier using digit-serial architecture. Silicon compilers exist which permit the human operator to specify the signal processing function in terms of a high level algebraic equation which is received by the silicon compiler and operated on, thereby to produce the mask set which will operate to generate an electronic integrated-circuit chip that implements the specified high-level algebraic function.
To carry out these objectives, it is necessary for silicon compilers to have available to them a library of cells which cells are capable of carrying out operations on data that are as wide as the desired digit size. For it to be feasible for silicon compilers to carry out these objectives, the library of basic cells which is required to implement these digit-serial operations, cannot be too large. Accordingly, an aspect of the invention is directed to a scheme of digital multiplier construction which uses basic cells and stacks bit slices to generate digital multipliers for any digit size. More particularly, an aspect of the invention is directed to augmenting the cell library for a silicon compiler so the compiler can construct digit-serial multipliers for any reasonable digit size specified by the human operator. The basic cells are often refered to as "tiles" and the arrangement of them on an integrated-circuit die is often refered to as "tiling".
An analysis of the digit-serial multiplier to be described in the present specification will reveal it to have features found in combinational array multipliers, known in the prior art. Such combinational array multipliers are described, for example, by J. P. Hayes on pages 246-248 of his book COMPUTER ARCHITECTURE AND ORGANIZATION, 2nd Ed., copyright 1988, 1978 by McGraw Hill, Inc., New York City, St. Louis, etc.